P5017 摆渡车

这道题我们先看一下数据范围:n500,m100,0ti4×106n≤500,m≤100,0≤t_i≤4×10^6

显然复杂度和n,mn,m有关,既然如此,我们考虑用tt的复杂度来解决此题吧。(此题解法不止一种)

我们用dp[i]dp[i]表示在ii时刻发车(不管是第几次),所有在ii时刻之前到达的人的等待时间之和。tot[i]tot[i]表示第ii时刻有多少人开始等车,显然有:

dp[i]=min(dp[j]+k=j+1itot[i](ik))   (jim)dp[i]=min(dp[j]+\sum_{k=j+1}^i tot[i]*(i-k))~~~(j ≤ i- m )

我们再考虑一下边界条件,MintMin_t表示最先到的一个人来的时间,显然有dp[Mint]=0dp[Min_t]=0MaxtMax_t表示最后一个人来的时间。最坏情况下,在最后一个人来的前一秒车开走了,那么总时间最多为Maxt+m1Max_t+m-1

最后,答案就是min(dp[i])   (MaxtiMaxt+m1)min(dp[i])~~~(Max_t≤i≤Max_t+m-1)(最后一个人开始等车)。

然后,我们就可以用t3t^3转移了。再看一下数据,得分3030

优化1

转移时的复杂度体现在求和,这个可以用前缀和优化。

我们用tot[i]tot[i]表示前ii时刻等车的人数之和(与前文定义不同),sum[i]sum[i]表示前ii时刻到达的人如果从0时刻开始等车,他们的时间之和。

那么,tot[i]tot[j]tot[i]-tot[j]就表示iijj这段时间里开始等车的人数之和,sum[i]sum[j]sum[i]-sum[j]表示第j+1j+1时刻到第ii时刻来到的人,从00时刻开始等车到他们来到的时间之和。(tot[i]tot[j])i(sum[i]sum[j])(tot[i]-tot[j])*i-(sum[i]-sum[j])就是j+1j+1ii时刻来到的人从开始等车到上车的时间之和,这就是我们转移时求的东西,处理前缀可以Θ(1)\Theta(1)转移。转移变为:

dp[i]=min(dp[j]+(tot[i]tot[j])i(sum[i]sum[j]))   (jim)dp[i]=min(dp[j]+(tot[i]-tot[j])*i-(sum[i]-sum[j]))~~~(j ≤ i- m )

总复杂度Θ(t2)\Theta(t^2),得分50。

优化2

我们对优化1的式子继续拆分,并将只与i有关的部分拿出提出来,得到:

dp[i]=min(dp[j]+tot[j]i+sum[j]))+tot[i]isum[i]   (jim)dp[i]=min(dp[j]+tot[j]*i+sum[j]))+tot[i]*i-sum[i]~~~(j ≤ i- m )

熟悉的同学可能会看出,这就是一道斜率优化的板题了。

转移只与dp[j]+tot[j]i+sum[j]dp[j]+tot[j]*i+sum[j]有关,我们考虑两个决策点u,vu,v,且uu优于vv,即:

dp[u]+tot[u]i+sum[u]<dp[v]+tot[v]i+sum[v]dp[u]+tot[u]*i+sum[u]<dp[v]+tot[v]*i+sum[v]

移项得:

dp[u]dp[v]+sum[u]sum[v]<(sum[v]sum[u])idp[u]-dp[v]+sum[u]-sum[v]<(sum[v]-sum[u])*i

u<vu<v时,sum[u]<sum[v]sum[u]<sum[v]

dp[u]dp[v]+sum[u]sum[v]sum[v]sum[u]<i\frac{dp[u]-dp[v]+sum[u]-sum[v]}{sum[v]-sum[u]}<i

u>vu>v时,sum[u]>sum[v]sum[u]>sum[v]

dp[u]dp[v]+sum[u]sum[v]sum[v]sum[u]>i\frac{dp[u]-dp[v]+sum[u]-sum[v]}{sum[v]-sum[u]}>i

xi=sum[i],yi=dp[i]+sum[i]x_i=sum[i],y_i=dp[i]+sum[i],则原式变为:

yuyvxuxv<i\frac{y_u-y_v}{x_u-x_v}<i

yuyvxuxv>i\frac{y_u-y_v}{x_u-x_v}>i

我们就可以用单调队列维护斜率,可以证明,一定是一个下凸包(即单调递增),具体可以看一下网上斜率优化。

最后,转移Θ(1)\Theta(1)实现,总复杂度Θ(t)\Theta(t),100分。

附上代码:

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 500;
const int MAXT = 4000000;
int n,m,x , Max_t;
int tot[ MAXT + 5 ] , sum[ MAXT + 5 ] , dp[ MAXT + 5 ];
int head = 1 , tail = 0;
int Queue[ MAXT + 5 ];

double delta_x( int u , int v ) {
	return tot[ v ] - tot[ u ] == 0 ? 1e-9 : tot[ v ] - tot[ u ];
}
double delta_y( int u , int v ) {
	return ( dp[ v ] + sum[ v ] ) - ( dp[ u ] + sum[ u ] );
}
double Slope( int u , int v ) {
	return delta_y( u , v ) / delta_x( u , v );
}

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&x);
		Max_t = max( Max_t , x );
		tot[ x ] ++ , sum[ x ] += x;
	}
	for( int i = 1 ; i <= Max_t + m - 1 ; i ++ ) {
		tot[ i ] += tot[ i - 1 ];
		sum[ i ] += sum[ i - 1 ];
	}
	
	for( int i = 0 ; i <= Max_t + m - 1 ; i ++ ) {
		if( i >= m ) {
			while( head < tail && Slope( Queue[ tail - 1 ] , Queue[ tail ] ) > Slope( Queue[ tail ] , i - m ) )
				tail --;
			Queue[ ++ tail ] = i - m;
		}
		while( head < tail && Slope( Queue[ head ] , Queue[ head + 1 ] ) <= i )
			head ++;
		dp[ i ] = tot[ i ] * i - sum[ i ];
		if( head <= tail ) dp[ i ] = min( dp[ i ] , dp[ Queue[ head ] ] + ( tot[ i ] - tot[ Queue[ head ] ] ) * i - sum[ i ] + sum[ Queue[ head ] ] );
	}
	int Ans = 0x3f3f3f3f;
	for( int i = Max_t ; i <= Max_t + m - 1 ; i ++ )
		Ans = min( Ans , dp[ i ] );
	printf("%d",Ans);
	return 0;
}